package org.chen.practice.middle;

/**
 * @Author chen
 * @Date 2023/7/17 23:59
 */

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 题目名称：无重复字符最长字串
 * 题目描述
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * 示例：
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 */
public class DiffCharMaxChild {
    public static void main(String[] args) {
        String l = "pwkwwwkew";
        System.out.println(lengthOfLongestSubstring(l));
    }

    // 最多没有多少重复字符

    /**
     * 滑动窗口
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> occ = new HashSet<>();
        int n = s.length();
        // rk右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk =-1,ans=0;
        for(int i=0;i<n;i++){
            // i是开始指针
            if(i != 0){
                // 回退一位,左指针向右移动一格，移除一个字符，
                // 移动窗口长度调整
                occ.remove(s.charAt(i-1));
            }
            // 获取字串，判断下一个字符是否重复，且不越界，rk时结束指针
            while(rk +1<n && !occ.contains(s.charAt(rk+1))){
                occ.add(s.charAt(rk+1));
                ++rk;
            }
            // 获取最长字串
            ans = Math.max(ans,rk-i+1);
        }
        return ans;
    }


    /**
     * 字符重复记录当钱最大字符字串长度，跳转到下一字符位置
     * 时间复杂度O(n)
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstringPro(String s) {
        HashMap<Character,Integer> occ = new HashMap<>();
        int n = s.length();
        int start =0,max=0;
        for(int end=0;end<n;end++){
            char ch = s.charAt(end);
            if(occ.containsKey(ch)){
                // 直接到下一字符位置
                start = Math.max(occ.get(ch)+1,start);
            }
            max = Math.max(end-start+1,max);
            occ.put(ch,end);
        }
        return max;
    }

    /**
     * 题干理解错误
     * @param
     * @return
     */
    public static int diffChar(String s) {
        Map<Character,String> tempMap = new HashMap<>();
        int clen =0;
        for(int i=0;i<s.length();i++){
            Character ckey = s.charAt(i);
            if(tempMap.containsKey(ckey)){

            }else{
                tempMap.put(ckey,"1");
                clen = clen+1;
            }
        }
        return clen;
    }
}
